package com.hdu.other.monotonyStack;


public class lc85 {


    class Solution {
        public int maximalRectangle(char[][] matrix) {
            int len = matrix[0].length;
            int[] nums = new int[len];
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < len; j++) {
                    if (matrix[i][j] == '0') nums[j] = 0;
                    else nums[j] = nums[j] + 1;
                }
                ans = Math.max(ans, maxSize(nums));
            }
            return ans;
        }

        int maxSize(int[] heights) {
            int n = heights.length;
            int[] stack = new int[n];
            int r = 0;
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                if (r == 0 || heights[stack[r - 1]] < heights[i]) {
                    stack[r++] = i;
                } else if (heights[stack[r - 1]] == heights[i]) {
                    r--;
                    stack[r++] = i;
                } else {
                    while (r > 0 && heights[i] < heights[stack[r - 1]]) {
                        int index = stack[--r];
                        int left = r == 0 ? -1 : stack[r - 1];
                        int width = i - left - 1;
                        ans = Math.max(ans, width * heights[index]);
                    }
                    stack[r++] = i;
                }
            }

            while (r > 0) {
                int index = stack[--r];
                int left = r == 0 ? -1 : stack[r - 1];
                int width = n - left - 1;
                ans = Math.max(ans, width * heights[index]);
            }

            return ans;
        }
    }
}
